#![allow(clippy::many_single_char_names)]

use std::cmp::max;

// #[must_use]
// pub fn is_prime(x: u128) -> bool {
//     for i in 2..x {
//         if x % i == 0 {
//             return false;
//         }
//     }
//     true
// }

#[must_use]
pub fn miller_rabin(x: u128) -> bool {
    UInt::miller_rabin(x)
}

#[must_use]
pub fn find_max_prime_factor(x: u128) -> u128 {
    let mut ans = 0;
    u128::find_max_prime_factor(x, &mut ans);
    ans
}

trait UInt {
    fn random() -> Self;

    fn gcd(a: Self, b: Self) -> Self;

    fn qmul(a: Self, b: Self, m: Self) -> Self;

    fn qpow(a: Self, b: Self, m: Self) -> Self;

    fn miller_rabin(x: Self) -> bool;

    fn pollard_rho(x: Self) -> Self;

    fn find_max_prime_factor(x: Self, mf: &mut Self);
}

impl UInt for u128 {
    fn random() -> Self {
        rand::random()
    }

    fn gcd(mut a: u128, mut b: u128) -> u128 {
        while b != 0 {
            let r = a % b;
            a = b;
            b = r;
        }
        a
    }

    #[inline(always)]
    fn qmul(a: u128, b: u128, m: u128) -> u128 {
        a.wrapping_mul(b) % m
    }

    fn qpow(mut a: u128, mut b: u128, m: u128) -> u128 {
        let mut r = 1;
        while b != 0 {
            if b & 1 != 0 {
                r = Self::qmul(r, a, m);
            }
            a = Self::qmul(a, a, m);
            b >>= 1;
        }
        r
    }

    fn miller_rabin(x: u128) -> bool {
        if x < 2 {
            return false;
        }
        if x % 2 == 0 {
            return x == 2;
        }
        if x % 3 == 0 {
            return x == 3;
        }

        let mut u = x - 1;
        let mut t = 0;
        while u % 2 == 0 {
            u /= 2;
            t += 1;
        }

        let test_times = 10;
        for _ in 0..test_times {
            let a = Self::random() % (x - 3) + 2;
            let mut v = Self::qpow(a, u, x);
            if v == 1 {
                continue;
            }

            let mut s = 0;
            while s < t {
                if v == x - 1 {
                    break;
                }
                v = Self::qmul(v, v, x);
                s += 1;
            }

            if s == t {
                return false;
            }
        }

        true
    }

    fn pollard_rho(x: u128) -> u128 {
        let mut s = 0;
        let mut t = 0;
        let c = Self::random() % (x - 1) + 1;
        let mut goal = 1;
        let mut val = 1;
        loop {
            for step in 1..=goal {
                t = (Self::qmul(t, t, x) + c) % x;
                val = Self::qmul(val, u128::abs_diff(t, s), x);
                if step % 127 == 0 {
                    let d = Self::gcd(val, x);
                    if d > 1 {
                        return d;
                    }
                }
            }
            let d = Self::gcd(val, x);
            if d > 1 {
                return d;
            }
            goal *= 2;
            s = t;
            val = 1;
        }
    }

    fn find_max_prime_factor(mut x: u128, mf: &mut u128) {
        if x <= *mf || x < 2 {
            return;
        }

        if Self::miller_rabin(x) {
            *mf = max(*mf, x);
            return;
        }

        let mut p = x;
        while p >= x {
            p = Self::pollard_rho(x);
        }
        while x % p == 0 {
            x /= p;
        }
        Self::find_max_prime_factor(x, mf);
        Self::find_max_prime_factor(p, mf);
    }
}
